/// 大整数高级数学运算
/// 
/// 

///|
suberror ModularArithmeticError String

/// 快速幂运算（二进制幂）
pub fn pow(self : BigInt, exponent : BigInt) -> BigInt {
  if exponent.is_negative() {
    abort("Negative exponent not supported")
  }
  
  if exponent.is_zero() {
    return BigInt::one()
  }
  
  if self.is_zero() {
    return BigInt::zero()
  }
  
  if self == BigInt::one() {
    return BigInt::one()
  }
  
  let mut result = BigInt::one()
  let mut base = self
  let mut exp = exponent
  
  while not(exp.is_zero()) {
    if exp.is_odd() {
      result = result * base
    }
    base = base * base
    exp = exp >>1
  }
  
  result
}

/// 检查是否为奇数
pub fn is_odd(self : BigInt) -> Bool {
  not(self.is_zero()) && (self.digits[0] & 1) == 1
}

/// 检查是否为偶数
pub fn is_even(self : BigInt) -> Bool {
  self.is_zero() || (self.digits[0] & 1) == 0
}

/// 模幂运算（快速模幂）
pub fn pow_mod(self : BigInt, exponent : BigInt, modulus : BigInt) -> BigInt {
  if modulus.is_zero() {
    abort("Modulus cannot be zero")
  }
  
  if exponent.is_negative() {
    abort("Negative exponent not supported")
  }
  
  if exponent.is_zero() {
    return BigInt::one() % modulus
  }
  
  let mut result = BigInt::one()
  let mut base = self % modulus
  let mut exp = exponent
  
  while not(exp.is_zero()) {
    if exp.is_odd() {
      result = (result * base) % modulus
    }
    base = (base * base) % modulus
    exp = exp>>1
  }
  
  result
}

/// 平方根（牛顿法）
pub fn sqrt(self : BigInt) -> BigInt {
  if self.is_negative() {
    abort("Cannot compute square root of negative number")
  }
  if self.is_zero() || self == BigInt::one() {
    return self
  }

  // 初始猜测值
  let mut x = self >> (self.bit_length() / 2)
  if x.is_zero() {
    x = BigInt::one()
  }
  while true {
    let next_x = (x + self / x) >> 1
    if next_x.op_greater_equal(x) {
      break x
    }
    x = next_x
  } else {
    x
  }
}
/// 获取位长度
pub fn bit_length(self : BigInt) -> Int {
  if self.is_zero() {
    return 0
  }
  
  let mut bits = (self.digits.length() - 1) * 32
  let mut top_digit = self.digits[self.digits.length() - 1]
  
  while top_digit > 0 {
    bits = bits + 1
    top_digit = top_digit >> 1
  }
  
  bits
}

/// 最大公约数（欧几里得算法）
pub fn gcd(self : BigInt, other : BigInt) -> BigInt {
  let mut a = self.abs()
  let mut b = other.abs()
  
  while not(b.is_zero()) {
    let temp = b
    b = a % b
    a = temp
  }
  
  a
}

/// 最小公倍数
pub fn lcm(self : BigInt, other : BigInt) -> BigInt {
  if self.is_zero() || other.is_zero() {
    return BigInt::zero()
  }
  
  (self * other).abs() / self.gcd(other)
}

/// 扩展欧几里得算法
/// 返回 (gcd, x, y) 使得 ax + by = gcd(a, b)
pub fn extended_gcd(self : BigInt, other : BigInt) -> (BigInt, BigInt, BigInt) {
  if other.is_zero() {
    return (self, BigInt::one(), BigInt::zero())
  }
  
  let (gcd, x1, y1) = other.extended_gcd(self % other)
  let x = y1
  let y = x1 - (self / other) * y1
  
  (gcd, x, y)
}

/// 模逆元
pub fn mod_inverse(
  self : BigInt,
  modulus : BigInt
) -> BigInt raise ModularArithmeticError {
  let (gcd, x, _) = self.extended_gcd(modulus)
  if gcd != BigInt::one() {
    raise ModularArithmeticError("Modular inverse does not exist")
  }
  let result = x % modulus
  if result.is_negative() {
    result + modulus
  } else {
    result
  }
}

///| 阶乘
pub fn BigInt::factorial(n : BigInt) -> BigInt {
  if n.is_negative() {
    abort("Factorial of negative number")
  }
  if n.is_zero() || n == BigInt::one() {
    return BigInt::one()
  }
  let mut result = BigInt::one()
  let mut i = BigInt::from_int(2)
  while i <= n {
    result = result * i
    i = i + BigInt::one()
  }
  result
}

///| 斐波那契数列
pub fn BigInt::fibonacci(n : BigInt) -> BigInt {
  if n.is_negative() {
    abort("Fibonacci of negative number")
  }
  
  if n.is_zero() {
    return BigInt::zero()
  }
  
  if n == BigInt::one() {
    return BigInt::one()
  }
  
  let mut a = BigInt::zero()
  let mut b = BigInt::one()
  let mut i = BigInt::from_int(2)
  
  while i <= n {
    let temp = a + b
    a = b
    b = temp
    i = i + BigInt::one()
  }
  
  b
}

///| 判断是否为质数（Miller-Rabin素性测试）
pub fn BigInt::is_prime(self : BigInt, k : Int) -> Bool {
  if self <= BigInt::one() {
    return false
  }
  
  if self <= BigInt::from_int(3) {
    return true
  }
  
  if self.is_even() {
    return false
  }
  
  // 将 n-1 写成 d * 2^r 的形式
  let mut d = self - BigInt::one()
  let mut r = 0
  
  while d.is_even() {
    d = d>>(1)
    r = r + 1
  }
  
  // 进行 k 轮测试
  for i = 0; i < k; i = i + 1 {
    let a = BigInt::random_range(BigInt::from_int(2), self - BigInt::from_int(2))
    let mut x = a.pow_mod(d, self)
    
    if x == BigInt::one() || x == self - BigInt::one() {
      continue
    }
    
    let mut composite = true
    for j = 0; j < r - 1; j = j + 1 {
      x = (x * x) % self
      if x == self - BigInt::one() {
        composite = false
        break
      }
    }
    
    if composite {
      return false
    }
  }
  
  true
}

///| 生成指定范围内的随机大整数（简单实现）
pub fn BigInt::random_range(min : BigInt, max : BigInt) -> BigInt {
  // 这是一个简化的实现，实际应用中需要更好的随机数生成器
  if min >= max {
    return min
  }
  let range = max - min
  let mut result = BigInt::zero()

  // 简单的线性同余生成器
  let mut seed = 12345
  for i = 0; i < range.digits.length(); i = i + 1 {
    seed = (seed * 1103515245 + 12345) % 0x80000000
    result = result + (BigInt::from_int(seed % (1 << 32)) << (i * 32))
  }
  min + result % range
}

///| 计算组合数 C(n, k)
pub fn BigInt::combination(n : BigInt, k : BigInt) -> BigInt {
  if k.is_negative() || k > n {
    return BigInt::zero()
  }
  
  if k.is_zero() || k == n {
    return BigInt::one()
  }
  
  // 优化：C(n, k) = C(n, n-k)
  let k_opt = if k > n - k { n - k } else { k }
  
  let mut result = BigInt::one()
  let mut i = BigInt::zero()
  
  while i < k_opt {
    result = result * (n - i) / (i + BigInt::one())
    i = i + BigInt::one()
  }
  
  result
}

///| 计算排列数 A(n, k)
pub fn BigInt::permutation(n : BigInt, k : BigInt) -> BigInt {
  if k.is_negative() || k > n {
    return BigInt::zero()
  }
  
  if k.is_zero() {
    return BigInt::one()
  }
  
  let mut result = BigInt::one()
  let mut i = BigInt::zero()
  
  while i < k {
    result = result * (n - i)
    i = i + BigInt::one()
  }
  
  result
}

///| 计算排列数 A(n, k)，允许重复
pub fn BigInt::permutation_with_repetition(n : BigInt, k : BigInt) -> BigInt {
  if n.is_negative() || k.is_negative() {
    return BigInt::zero()
  }
  
  let mut result = BigInt::one()
  let mut i = BigInt::zero()
  
  while i < k {
    result = result * n
    i = i + BigInt::one()
  }
  
  result
}

